home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93b.txt / 000126_icon-group-sender _Mon May 24 16:17:47 1993.msg < prev    next >
Internet Message Format  |  1993-06-16  |  2KB
  1. Received: from owl.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Tue, 1 Jun 1993 15:03:45 MST
  2. Received: by owl.cs.arizona.edu; Tue, 1 Jun 1993 15:03:44 MST
  3. Date: 24 May 93 16:17:47 GMT
  4. From: mcsun!uknet!warwick!zaphod.crihan.fr!univ-lyon1.fr!scsing.switch.ch!news.unige.ch!NewsWatcher!user@uunet.uu.net  (Boris Borcic)
  5. Organization: University of Geneva
  6. Subject: Yet another variation on queens (was Icon vs Prolog)
  7. Message-Id: <borbor-240593173741@129.194.82.105>
  8. References: <9305171538.AA58087@enlil.premenos.sf.ca.us>
  9. Sender: icon-group-request@cs.arizona.edu
  10. To: icon-group@cs.arizona.edu
  11. Status: R
  12. Errors-To: icon-group-errors@cs.arizona.edu
  13.  
  14. First of all, I would like to thank all who replied to my
  15. question on Icon and Prolog.
  16.  
  17. In article <9305171538.AA58087@enlil.premenos.sf.ca.us>, Ken Walker
  18. <kwalker@shara.premenos.sf.ca.us> wrote:
  19. [...]
  20. > Icon, on the other hand,
  21. > has more features and as an imperative languages gives you more
  22. > control and more flexibility. It might be interesting to look at
  23. > specific problems.
  24. > 
  25. > Ken Walker, kwalker@premenos.sf.ca.us
  26.  
  27. One example I have in mind is YAVQ : yet another variation on the
  28. queens problem. The problem :
  29.  
  30. 1) Write a search algorithm that generates the first solution only
  31.    (according to the lexicographic order on permutations), for
  32.    each family of rotated and/or reflected solutions, by *pruning*
  33.    the search tree ASAP rather than testing the generated solutions.
  34.  
  35. 2) Write a search algorithm that chooses the next choicepoint
  36.    among the remaining unoccupied rows *and* columns according to
  37.    some criterion (say, that the breadth of the choicepoint is
  38.    minimal).
  39.  
  40. 3) Write a 3D version of 1+2, e.g. N^2 queens in N^3 cubic "board"
  41.    (are there any 3d solutions to N^2 queens ? should one use plane 
  42.     diagonals, 3d diagonals, or both ?)
  43.  
  44.    Note that the number of symmetries usable to constrain the
  45.    search raises from 8 in 2d to 48 in 3d.
  46.  
  47. I have no code to propose, and indeed did not completely think this
  48. through. But I could find no easy way to maintain the data structure
  49. for implementing [2] (in the context of [1]) in Prolog, except
  50. by not using the in-built backtracking at all. If memory serves,
  51. the problem is both the absence of globals and the "total data
  52. amnesia" in Prolog, as noted by one of the previous posters.
  53.  
  54. Regards,
  55.  
  56. Boris Borcic
  57.